package com.wyr.zuoshen.zuoshen1.p2;

public class SheelSort {
    /**
     * 希尔排序是插入排序的升级
     * 可以采用某些技巧对数组进行预处理，聪明的科学家想到了一种分组排序的方法，以此对数组进行一定的预处理
     * 所谓分组，就是让元素两两一组，同组两个元素之间的跨度，是数组总长度的一半
     * 如果数组的长度是8，那么分组的跨度就是4，2，1
     * 例如：
     * 5  8  6  3  9  2  1  7
     * 第一次分组就是每隔d=arr.length/2=4个元素分为一组
     * 也就是：5  9
     *        8  2
     *        6  1
     *        3  7
     * 这四组，对于每一组分别进行插入排序
     * 获得：5  2  1  3  9  8  6  7
     *
     * 第二次分组就是每隔d=d/2=2个元素分为一组
     * 也就是：5  1  9  6
     *        2  3  8  7
     * 这两组，对于每一组分别进行插入排序
     * 获得：1  2  5  3  6  7  9  8
     *
     * 第三次分组就是每隔d=d/2=1个元素分为一组
     * 也就是：1  2  5  3  6  7  9  8
     * 这一组，对于这一组进行插入排序
     * 获得：1  2  3  4  5  6  7  8  9
     *
     * 其中的d就是希尔增量
     */

    public static void sheelSort(int [] array){
        //希尔排序的增量
        int d=array.length;
        while (d>1){
            //使用希尔增量的方式，即每次折半
            d=d/2;
            for(int x=0;x<d;x++){ //分的组
                for(int i=x+d;i<array.length;i+=d){ //i代表要插入的数的下标
                    //里面的逻辑其实就是优化后的插入排序的逻辑
                    int temp=array[i];
                    int j=i-d;
                    for(;j>=0&&temp<array[j];j-=d){
                        array[j+d]=temp;
                    }
                    array[j+d]=temp;
                }
            }
        }
    }
}
